package vip.zhenzicheng.algorithm.sort;

import vip.zhenzicheng.algorithm.util.ArrayUtils;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author zhenzicheng
 * @date 2022-06-08 12:17
 */
public class ShellSort {

  public static void main(String[] args) {
    int[] randomArray = ArrayUtils.getRandomArray(10, 30);
    shellSort(randomArray);
    System.out.println(Arrays.toString(randomArray));
  }

  public static void shellSort(int[] arr) {
    int N = arr.length;
    int gap = N / 2, temp;

    while (gap > 0) {
      for (int i = gap; i < N; i++) {
        temp = arr[i];
        // 组内已被排序的数据索引
        int preIndex = i - gap;
        // 在组内已被排序过数据中倒序寻找合适的位置
        while (preIndex >= 0 && arr[preIndex] > temp) {
          arr[preIndex + gap] = arr[preIndex];
          preIndex -= gap;
        }
        // 找到合适位置后，插入
        arr[preIndex + gap] = temp;
      }

      gap /= 2;
    }
  }
}
